package com.leet.code.simple_array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description:    1399.统计最大组的数目
 * @author: WYG
 * @time: 2021/1/3 21:12
 */

public class CountLargestGroup {

    public int fastest_countLargestGroup(int n) {
        int ans = 0, max = 1;
        int[] count = new int[n +  1];// 统计数位和有多少
        int[] sum = new int[n + 1]; //计算1-n各个元素的数位和，例如数字i的数位和是sum[i / 10] + i % 10

        for(int i = 1; i <= n; i++){
            sum[i] = sum[i / 10] + i % 10;
            count[sum[i]]++;
            if(count[sum[i]] > max)
                max = count[sum[i]];
        }

        for(int num : count) ans += num == max ? 1 : 0;

        return ans;
    }


    public int fast_countLargestGroup(int n) {
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int maxValue = 0;
        for (int i = 1; i <= n; ++i) {
            int key = 0, i0 = i;
            while (i0 != 0) {
                key += i0 % 10;
                i0 /= 10;
            }
            hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
            maxValue = Math.max(maxValue, hashMap.get(key));
        }
        int count = 0;
        for (Map.Entry<Integer, Integer> kvpair : hashMap.entrySet()) {
            if (kvpair.getValue() == maxValue) {
                ++count;
            }
        }
        return count;
    }


    public int countLargestGroup(int n) {
        int res = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            List<Integer> temp = new ArrayList<>();
            int sum = 0;
            while (i > 0) {
                int remainder = i % 10;
                sum += remainder;
                i = i / 10;
            }
            if (map.containsKey(sum)) {
                temp = map.get(sum);
                temp.add(i);
                map.put(sum, temp);
            } else {
                temp.add(i);
                map.put(sum, temp);
            }
        }
        for (Map.Entry entry : map.entrySet()) {
            if (((List)entry.getValue()).size() > res) {
                res = ((List)entry.getValue()).size();
            }
        }
        return res;
    }
}
